package com.yeung.exam;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 利用递归, 将左右子树交换
 */
public class 字节_二叉树的镜像 {
    public static void mirror(ZTreeNode root) {
        if (root == null) return;
        //将左子树 施行镜像操作
        mirror(root.left);
        //将右子树施行镜像操作
        mirror(root.right);
        //交换左右节点
        ZTreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }

    public static ZTreeNode createTree(String[] data, ZTreeNode root, int index) {
        if (2 * index + 1 < data.length) {
            //递归创建左孩子
            if (2 * index + 1 < data.length) {
                ZTreeNode left = new ZTreeNode(data[2 * index + 1]);
                root.left = left;
                left = createTree(data, root.left, 2 * index + 1);
            }

            //递归创建右孩子
            if (2 * index + 2 < data.length) {
                ZTreeNode right = new ZTreeNode(data[2 * index + 2]);
                root.right = right;
                right = createTree(data, root.right, 2 * index + 2);
            }

        } else {
            root.left = root.right = null;
        }
        return root;
    }

    public static class ZTreeNode {
        String val;
        ZTreeNode left;
        ZTreeNode right;

        public ZTreeNode(String val) {
            this.val = val;
        }
    }

    /**
     * 层次遍历
     *
     * @param root
     */
    public static void order(ZTreeNode root) {
        Queue<ZTreeNode> queue = new LinkedList<>();
        queue.add(root);
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            int count = queue.size();
            while (count > 0) {
                ZTreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
                sb.append(node.val);
                sb.append(" ");
                count--;
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] data = sc.nextLine().split(" ");
        if (data.length > 0) {
            ZTreeNode tree = createTree(data, new ZTreeNode(data[0]), 0);
            mirror(tree);
            order(tree);
        }
    }


}



